1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include <cstdio>
#include <algorithm>
#include <cmath>
const int maxn = 1e5 + 5;
using namespace std;
int Max[maxn][21], n, Q;
int main(){
scanf("%d%d", &n, &Q);
for (int i = 1; i <= n; i++) scanf("%d", Max[i]);
for (int j = 1; j <= 21; j++)
for (int i = 1; (1 << j) + i - 1 <= n; i++)
Max[i][j] = max(Max[i][j - 1], Max[i + (1 << (j - 1))][j - 1]);
while (Q--){ int l, r;
scanf("%d%d", &l, &r);
int k = (int)log2(r - l + 1);
printf("%d\n", max(Max[l][k], Max[r - (1 << k) + 1][k]));
}
return 0;
}
|